package LearnDataStructure.c_树结构.有序树.B树;

import java.util.LinkedList;
import java.util.List;

/**
 * @version: 1.0
 * @Author: wuqiu
 * @date: 2023-07-19 16:21
 * @description: LeetcodeLearnAlgorithm -> LearnDataStructure.c_树结构.有序树.B树
 */
public class MyBTreePlus<K extends Comparable<K>> {
    // 度数，取以2开始的自然数
    public int degree = 2;
    // 阶数，通常取大于3的偶数;这里等于4
    public int order = 2 * degree;
    // 关键字个数上界;意义是“阶数 - 1”
    public int max = order - 1;//这里等于3
    /*
    关键字个数下界;如果阶数不是由degree得来的而是直接设定的，那么阶数有可能为奇数；
    无论阶数奇偶，除以2再向上取整的结果，设为temp，temp-1就是关键字个数的下界；
    temp是有意义的；因为除了叶子节点和根节点，其他节点的子节点数 必须  >= temp(这里等于2)
     */
    public int min = (int) Math.ceil(order / 2) - 1;//这里等于1
    //根节点，目前所有属性都是空
    public BTreeNode<K> root = new BTreeNode<K>();
    //全树的关键字个数；也是树的
    public int size = 0;

    public MyBTreePlus() {
    }

    /**
     * 用户调用增加方法
     *
     * @param key
     * @return
     */
    public boolean insert(K key) {
        boolean result = insert(root, key);
        if (result) {
            size++;
        }
        return result;
    }

    /**
     * 内部调用增加方法
     *
     * @param root
     * @param key
     * @return
     */
    public boolean insert(BTreeNode<K> root, K key) {
        //健壮性判断
        if (root == null || key == null) {
            return false;
        }
        // 根结点为满而需要分裂的特殊情形
        if (root.N == max) {//max == 3, 阶数 == 4
            // 制造新的根结点，newNode,高度增加
            BTreeNode<K> newNode = new BTreeNode<K>();
            // 更新根节点，newNode
            this.root = newNode;
            newNode.addNode(root);//此时新root只有一个child
            newNode.leaf = false;

            //root必须2个child，所以需要对新root进行分裂
            split(newNode, 0);
            //
            return insertWithoutFull(newNode, key);
        } else {
            // 一般情况
            return insertWithoutFull(root, key);
        }
    }

    /**
     * 对满关键字的节点进行分裂
     * 仅仅是分裂，不包含新key的插入
     * i代表当前target这个节点的第i索引处的子节点是满的
     *
     * 分裂其实有不同算法，自顶而下和自底而上
     * 本方法采用自顶而下算法，即每次插入新关键字时，沿着树向下查找所属位置，
     * 依次分裂沿途每个满结点(包括叶结点)，然后插入该关键字；
     * 自底而上算法稍微复杂点，它是在找到新关键字所属位置(叶结点)后分裂该叶结点(满的)并插入关键字，
     * 因为每次分裂后其父结点关键字数量就会加1，因此继续分裂父结点直至首个非满结点为止
     * @param target
     * @param i
     */
    public void split(BTreeNode<K> target, int i) {
        BTreeNode<K> leftNode = target.getNode(i);//在newNode视角看，leftNode就是旧root
        //分裂出的节点，目前是空，需要填入属性
        BTreeNode<K> rightNode = new BTreeNode<K>();
        //填属性leaf...
        rightNode.leaf = leftNode.leaf;//在newNode视角看，leftNode.leaf == false
        /*
        分裂后的两个子结点(leftNode,rightNode)每个的关键字个数，其实就是BTree允许的最小关键字个数(m/2 - 1);这是分裂的规定
        因为被分裂的节点的关键字是满的，即在这里等于了3
        那么裂出来的leftNode.N = 1    rightNode.N = 1
        不会越界
        填属性N......在newNode视角看，rightNode.N = 1
         */
        rightNode.N = min;

        /*
        处理分裂后的新增子结点以及原子结点
        因为分裂后的两个节点，N设定死了为min，所以终止循环条件是j < min
         */
        for (int j = 0; j < min; j++) {
            /*
            注意：这里不能使用api中add(i, e)方法添加元素
            j + min代表跳过min个数据
            在此之上(j + min + 1)代表故意跳过了一个元素，
            如果j从0开始的话，这个元素在leftNode中的keyList中的索引就是min
            这个索引的元素，将来就会被上浮
             */
            rightNode.addKey(leftNode.getKey(j + min + 1));
        }
        /*
        min + 1实际上就是等于 m/2
        在这里就是min + 1 = 4/2 = 2
        因为在newNode角度看
        满的旧root的child数量一定比关键字数量多1，因为此时满了
        所以一定会有“旧root.N == 3 && 旧root.nodeList.size() == 4”
        好，前置知识讲完了，下面开始：
        由于leftNode与rightNode的N被设定死了 == min == 1
        那么nodeList同样被设定死了 == min + 1 == 2；因此循环跳出条件是min + 1
        我们仍然想要跳过索引min绑定的node，所以我们仍然(j + min + 1)
         */
        if (!leftNode.leaf) {
            for (int j = 0; j < min + 1; j++) {
                rightNode.addNode(leftNode.getNode(j + min + 1));
            }
        }
        /*
        从newNode视角看，target就是newNode;此时newNOde是空的 N == 0;
        而i传进来就是0
        i代表当前target这个节点的第i索引处的子节点是满的
         */
        if (i == target.N) {
            /*
            当target的索引3的子节点是满的；(因为i是索引，而且根据满了，target.N必然 == max == 3)
            所以我们上面故意跳过的那个元素(索引为min的元素)
            就是即将要上浮的元素(索引为min的元素)！
            就是即将要填入newNode的元素(索引为min的元素)！
            关键字及子结点不需要移位，或者说，不需要特别指定索引
             */
            target.addKey(leftNode.getKey(min));
            target.addNode(rightNode);//仅仅完成了“分裂结果的右边”的添加；此时还没处理左边
        } else {
            /*
            i代表当前target这个节点的第i索引处的子节点是满的
            别的索引上的子节点满了
            关键字及子结点需要移位!
            上面故意跳过的那个元素(索引为min的元素)需要指定填入到索引i处
            因为rightNode是right，rightNode的关键字和node都比“故意跳过的那个元素(索引为min的元素)”要“大”
            所以需要指定填入到索引i+1处，即右边
             */
            target.addKey(i, leftNode.getKey(min));
            target.addNode(i+1,rightNode);
        }
        //做完了右边的添加，给target.N更新！
        target.N++;

        /*
        接下来对左边进行处理
        要删除已经分裂出去的key和node
        分裂出去key的数量是 min + 1个上浮了的索引 ，所以是 min + 1
        分裂出去的node的数量是同理
         */
        for (int j = 0; j < min + 1; j++) {
            leftNode.removeLastKey();
        }
        if (!leftNode.leaf) {
            for (int j = 0; j < min + 1; j++) {
                leftNode.removeLastNode();
            }
        }
        //删除操作完成后，更新leftNode.N
        leftNode.N = min;
    }

    /**
     * 真正插入key的方法，插入位置永远是叶子节点
     * 本方法是指，向以非满结点参数root，为根的树插入关键字key
     * 并不是指参数root为根的树其所有结点都非满
     * @param root
     * @param key
     * @return
     */
    public boolean insertWithoutFull(BTreeNode<K> root,K key) {
        //健壮性判断
        if (root == null || key == null) {
            return false;
        }
        //关键字的下标
        int index = root.N - 1;
        //当前递归出口；此次递归的root是叶子节点
        if (root.leaf) {
            /*
            当前索引index没越界
            而且root.keyList同索引处的元素比key“大”
             */
            while (index >= 0 && key.compareTo(root.getKey(index)) < 0) {
                index--;
            }
            /*
            跳出循环的index,要么 == -1，要么是最后一个“小于”key的元素的索引A
            只要indedx < root.N - 1,就代表keyLIst中存在“大于”key的元素，只是不知道几个
            无论index == -1 还是 A, key要插入的位置永远是index+1
             */
            if (index < root.N - 1) {
                root.addKey(index+1,key);
            /*
            否则，keyList中不存在“大于”key的元素
            代表着key是最大的，理应当在最后
             */
            } else {
                root.addKey(key);
            }
            //至此，key添加完成也成功，更新root.N
            root.N++;
            return true;
        //普通递归
        } else {
            /*
            当前索引index没越界
            而且root.keyList同索引处的元素比key“大”
             */
            while (index >= 0 && key.compareTo(root.getKey(index)) < 0) {
                index--;
            }
            /*
            跳出循环的index,要么 == -1，要么是最后一个“小于”key的元素的索引A
            无论index == -1 还是 A, key要插入的位置永远是index+1
             */
            index++;
            /*
            判断要递归的下一个节点getNode(index)是否满了
            为什么必须是getNode(index)？
            因为keyList的索引与nodeList的索引是有映射关系的
             */
            if (root.getNode(index).N == max) {//root的索引index的子节点因为满了需要分裂
                //分裂目标节点
                split(root,index);
                /*
                分裂完成后，root也就是当前本次递归中的节点，的keyList已经得到更新
                判断更新后的keyList的索引index处的元素是否“小于”key
                如果小于，那么进行一次++，
                 */
                if (key.compareTo(root.getKey(index)) > 0) {
                    index++;
                }
            }
            return insertWithoutFull(root.getNode(index),key);
        }
    }

    /**
     * 用户调用删除方法
     * @param key
     * @return
     */
    public boolean delete(K key) {
        Result<K> result = search(key);
        if (result == null) {
            return false;
        }
        delete(root, key);
        size--;
        return true;
    }

    /**
     * 内部调用删除方法
     * @param root
     * @param key
     */
    public void delete(BTreeNode<K> root, K key) {
        int index = 0;
        //index没有越界，keyList索引index处的元素"小于"key
        while (index < root.N && key.compareTo(root.getKey(index)) > 0) {
            index++;
        }
        /*
        跳出循环，要么index == root.N, 要么此时index的元素"等于"key，要么此时index的元素是第一个“大于”key的
         */
        if (index < root.N && key.compareTo(root.getKey(index)) == 0) {
            //key存在当前节点root中
            if (root.leaf) {                                            //情形1：root找到key,root是叶子节点
                root.keyList.remove(index);
                root.N--;
            } else {
                BTreeNode<K> leftNode = root.getNode(index);//当前要删除key的左边
                BTreeNode<K> rightNode = root.getNode(index+1);//当前要删除key的右边
                if (leftNode.N > min) {                                 //情形2-a：root找到key,root非叶子节点，target紧左孩子富有
                    K newKey = leftNode.keyList.getLast();
                    root.keyList.remove(index);
                    root.addKey(newKey);
                    delete(leftNode,newKey);
                } else if (rightNode.N > min) {                         //情形2-b：root找到key,root非叶子节点，target紧右孩子富有
                    K newKey = rightNode.keyList.getFirst();
                    root.keyList.remove(index);
                    root.addKey(newKey);
                    delete(rightNode,newKey);
                } else {                                                //情形2-c：root找到key,root非叶子节点，target没有富有的紧邻孩子
                    leftNode.addKey(key);
                    leftNode.N++;
                    for (int i = 0; i < min; i++) {
                        leftNode.addKey(rightNode.getKey(i));
                        leftNode.N++;
                    }
                    if (!leftNode.leaf) {
                        for (int i = 0; i < min + 1; i++) {
                            leftNode.addNode(rightNode.getNode(i));
                        }
                    }
                    root.keyList.remove(index);
                    root.nodeList.remove(index+1);//这里也可以看作删了rightNode
                    root.N--;
                    if (root.N == 0) {//说明入参root是根结点
                        // 树的高度缩减1
                        this.root = leftNode;
                    }
                    delete(leftNode,key);
                }
            }
        } else {//要么index == root.N，要么此时index的元素是第一个“大于”key的；index不会越界
            //一定能获得root.getNode(index)
            BTreeNode<K> childNode = root.getNode(index);
            if (childNode.N == min) {
                if (index > 0 && root.getNode(index-1).N > min) {               //情形3-a：root未找到key,root非叶子节点，key有可能在childNode中，childNode紧左兄弟富有
                    // 不论key是在childNode中还是在childNode的子树中，总是保证本次迭代后childNode至少min+1个关键字
                    BTreeNode<K> leftNode = root.getNode(index-1);
                    childNode.keyList.addFirst(root.getKey(index-1));
                    childNode.N++;
                    root.keyList.set(index-1,leftNode.keyList.removeLast());
                    leftNode.N--;
                    if (!childNode.leaf) {// 左邻兄弟结点的最后子结点也要借过去
                        childNode.nodeList.addFirst(leftNode.nodeList.removeLast());
                    }
                    delete(childNode,key);
                } else if (index < root.N && root.getNode(index+1).N > min) {   //情形3-b：root未找到key,root非叶子节点，key有可能在childNode中，childNode紧右兄弟富有
                    BTreeNode<K> rightNode = root.getNode(index+1);
                    childNode.keyList.addLast(root.getKey(index));
                    childNode.N++;
                    root.keyList.set(index,rightNode.keyList.removeFirst());
                    rightNode.N--;
                    if (!childNode.leaf) {// 右邻兄弟结点的第一个子结点也要借过去
                        childNode.nodeList.addLast(rightNode.nodeList.removeFirst());
                    }
                    delete(childNode,key);
                } else {
                    // childNode的相邻兄弟结点无可借关键字(注意：肯定有相邻兄弟结点)
                    // 当前结点要么是根结点，要么关键字个数必然大于min
                    // 当前结点不可能是关键字个数为min的非根结点的内部结点，因为前面已经保证了关键字个数至少min+1
                    if (index > 0) {                                            //情形3-c：root未找到key,root非叶子节点，key有可能在childNode中，childNode无富有紧邻兄弟
                        BTreeNode<K> leftNode = root.getNode(index-1);
                        childNode.keyList.addFirst(root.keyList.remove(index-1));
                        root.N--;
                        childNode.N++;
                        for (int i = min - 1; i >= 0; i--) {
                            childNode.keyList.addFirst(leftNode.keyList.get(i));
                            childNode.N++;
                        }
                        if (!childNode.leaf) {
                            for (int i = min; i >= 0; i--) {
                                childNode.nodeList.addFirst(leftNode.nodeList.get(i));
                            }
                        }
                        root.nodeList.remove(index-1);
                    } else if (index < root.N) {                                //情形3-d：root未找到key,root非叶子节点，key有可能在childNode中，childNode无富有紧邻兄弟
                        BTreeNode<K> rightNode = root.getNode(index+1);
                        childNode.keyList.addLast(root.keyList.remove(index));
                        root.N--;
                        childNode.N++;
                        for (int i = 0; i <= min - 1; i++) {
                            childNode.keyList.addLast(rightNode.keyList.get(i));
                            childNode.N++;
                        }
                        if (!childNode.leaf) {
                            for (int i = 0; i <= min; i++) {
                                childNode.nodeList.addLast(rightNode.nodeList.get(i));
                            }
                        }
                        root.nodeList.remove(index+1);
                    }
                    if (root.N == 0) {// 说明入参root是根结点
                        // 树的高度缩减1
                        this.root = childNode;
                    }
                    delete(childNode,key);
                }
            } else {
                delete(childNode ,key);
            }
        }
    }

    /**
     * 用户调用查询方法
     * @param key
     * @return
     */
    public Result<K> search(K key) {
        return search(root, key);
    }

    /**
     * 内部调用查询方法
     * @param root
     * @param key
     * @return
     */
    public Result<K> search(BTreeNode<K> root, K key) {
        //健壮性判断
        if (root == null || key == null) {
            return null;
        }
        int index = 0;
        //index没有越界，keyList索引index处的元素"小于"key
        while (index < root.N && key.compareTo(root.getKey(index)) > 0) {
            index++;
        }
        //跳出循环，当前index要么 == root.N, 要么当前第一个元素“大于”key；要么相等
        if (index < root.N && key.compareTo(root.getKey(index)) == 0) {
            //找到了：相等
            return new Result<K>(root,index);
        } else if (root.leaf) {
            //如果当前已经是叶子节点，没有递归可以用了，就代表没找到
            return null;
        } else {
            //递归，向下一层寻找key；getNode(index)一定不会越界
            return search(root.getNode(index),key);
        }
    }

    /**
     * 用户调用前序遍历方法
     */
    public void preOrder() {
        preOrder(root);
    }

    /**
     * 内部调用前序遍历方法
     * @param root
     */
    public void preOrder(BTreeNode<K> root) {
        for (int i = 0; i < root.N; i++) {
            System.out.print(root.getKey(i) + " ");
        }
        if (!root.leaf) {
            for (int i = 0; i <= root.N; i++) {
                preOrder(root.getNode(i));
            }
        }
    }

    /**
     * 表示关键字位置的类
     *
     * @param <U>
     */
    public static class Result<U extends Comparable<U>> {
        public BTreeNode<U> node;
        public int index;

        public Result(BTreeNode<U> node, int index) {
            this.node = node;
            this.index = index;
        }

        @Override
        public String toString() {
            return "Result{" +
                    "node=" + node +
                    ", index=" + index +
                    '}';
        }
    }

    /**
     * B树节点类
     *
     * @param <V>
     */
    public static class BTreeNode<V extends Comparable<V>> {
        // 关键字个数
        public int N;
        // 是否叶结点
        public boolean leaf = true;
        // 关键字列表
        public LinkedList<V> keyList = new LinkedList<V>();
        // 子结点列表
        public LinkedList<BTreeNode<V>> nodeList = new LinkedList<BTreeNode<V>>();

        public BTreeNode() {
        }

        public void addKey(V key) {
            keyList.add(key);
        }

        public void addKey(int index, V key) {
            keyList.add(index, key);
        }

        public void addNode(BTreeNode<V> node) {
            nodeList.add(node);
        }

        public void addNode(int index, BTreeNode<V> node) {
            nodeList.add(index, node);
        }

        public V getKey(int index) {
            return keyList.get(index);
        }

        public BTreeNode<V> getNode(int index) {
            return nodeList.get(index);
        }

        public void removeLastKey() {
            keyList.removeLast();
        }

        public void removeLastNode() {
            nodeList.removeLast();
        }

        @Override
        public String toString() {
            return "BTreeNode{" +
                    "N=" + N +
                    ", leaf=" + leaf +
                    ", keyList=" + keyList +
                    ", nodeList=" + nodeList +
                    '}';
        }
    }
}
